摘要什么是超像素超像素的评价标准具体计算公式的 bench markBoundary RecallUndersegmentation ErrorAchievable Segmentation AccuracyExplained VariationCompactnessIntra-Cluster VariationMean Distance to EdgeContour Density经典算法 SLIC针对经典算法的改进SEEDS 算法颜色能量分布项边界能量项算法复杂度ETPS 算法claim 点马尔科夫随机场(MRF)针对 SLIC 产生超像素不连续问题的改进针对 SEEDS 方法的改进ETPS 算法过程

摘要

本文是研究生课程图像处理期末作业,内容是了解并入门超像素算法原理,主要介绍了超像素的评测标准,经典算法 SLIC,讨论了 SLIC 算法中的不足之处,以及 SLIC 的两个有效的改进算法 SEEDS 和 ETPS。

什么是超像素

超像素概念是2003年Xiaofeng Ren提出和发展起来的图像分割技术。

Ren, Malik. Learning a classification model for segmentation[C]. international conference on computer vision, 2003: 10-17.

是指具有相似纹理、颜色、亮度等特征的相邻像素构成的有一定视觉意义的不规则像素块。它利用像素之间特征的相似性将像素分组,用少量的超像素代替大量的像素来表达图片特征,很大程度上降低了图像后处理的复杂度,所以通常作为分割算法的预处理步骤。

Den Bergh M V, Boix X, Roig G, et al. SEEDS: Superpixels Extracted Via Energy-Driven Sampling[J]. International Journal of Computer Vision, 2015, 111(3): 298-314.

超像素的评价标准

Stutz D, Hermans A, Leibe B, et al. Superpixels: An evaluation of the state-of-the-art[J]. Computer Vision and Image Understanding, 2018: 1-27.

从直观上来看,大多数超像素相关论文的作者都赞同以下的评价标准。

根据超像素的一些实际应用,超像素作为预处理步骤,理论上应该要能够提升后续步骤的性能。

具体计算公式的 bench mark

超像素是图像分割的一种变种,超像素分割属于图像分割(image segmentation)之中的过分割(over segmentation)。所以很多超像素的论文实验部分都是借助于图像分割中的评价标准。

Boundary Recall

Martin D, Fowlkes C C, Malik J, et al. Learning to detect natural image boundaries using local brightness, color, and texture cues[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26(5): 530-549.

度量的是边界附着,文章提出使用 precision-recall curves 来度量图像分割中边界检测的性能。作者将边界检测定义为一个区分非边界和边界像素的分类问题,将边界像素视为正例,非边界像素视为负例,这样就可以套用经典的 precision-recall curves 的计算方法来展现边界检测的优劣。作者给出了相应的 ground truth 数据集进行比对。

Martin D, Fowlkes C C, Tal D, et al. A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics[C]. international conference on computer vision, 2001: 416-423.

Undersegmentation Error

Levinshtein A, Stere A, Kutulakos K N, et al. TurboPixels: Fast Superpixels Using Geometric Flows[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009, 31(12): 2290-2297.

度量的是边界附着,过度分割错误,当超像素不能很好的拟合 ground truth 的时候,就会有多出来的部分并不是 ground truth,称之为过度分割的部分,这个误差越小越好。


Achievable Segmentation Accuracy

Liu M, Tuzel O, Ramalingam S, et al. Entropy rate superpixel segmentation[C]. computer vision and pattern recognition, 2011: 2097-2104.

度量的是边界附着,这个计算公式很简单,计算的是超像素分割中的正确分割的面积的比例,接近于1最好。

Explained Variation

Moore A P, Prince S J, Warrell J, et al. Superpixel lattices[C]. computer vision and pattern recognition, 2008.

度量的是紧凑度,这个也很好理解,计算的是超像素分割之后图像的方差和原始的方差的比值,接近于1最好。

Compactness

Schick A, Fischer M, Stiefelhagen R, et al. Measuring and evaluating the compactness of superpixels[C]. international conference on pattern recognition, 2012: 930-934.

度量的是紧凑度,将每个超像素的面积与具有相同周长的圆的面积进行比较。

Intra-Cluster Variation

W. Benesova, M. Kottman, Fast superpixel segmentation using morphological processing, in: Conference on Machine Vision and Machine Learning, 2014.

度量的是紧凑度,每个超像素的类内均值方差,当然是越小越好,长条状的超像素的方差会比较大。

Mean Distance to Edge

W. Benesova, M. Kottman. Fast superpixel segmentation using morphological processing. Conference on Machine Vision and Machine Learning, 2014.

度量的是边界附着,ground truth 中的每个像素到超像素分割出来的边界的距离。

Contour Density

Machairas V, Decenciere E, Walter T, et al. Waterpixels: Superpixels based on the watershed transformation[C]. international conference on image processing, 2014: 4343-4347.

度量的是分割的紧凑度,计算的是,图像中被染色为边界的像素,即超像素之间的像素。比例越小越好。

经典算法 SLIC

SLIC 的实现原理非常简单,主要是在 k-mean 的算法过程的基础上进行的改动,因此阅读该论文先要对 k-mean 算法有认真的了解。SLIC 对 k-mean 的改动的地方有距离度量,是色彩空间的欧几里得距离,是像素平面空间的欧几里得距离:

 

以及聚类搜索空间由原来的全局空间变成 大小的局部空间:

k-mean 搜索空间和 SLIC 搜索空间对比

 

 

初始化在图像空间上进行均匀的撒下聚类中心的种子,然后按 k-mean 算法步骤运行,最终将像素的颜色修改为对应聚类中心的颜色,这样就完成了超像素的工作。

很多人已经对 SLIC 理解透彻,相关的代码和实现在 github 上也能找到,作者的主要贡献在于:

一是生成的超像素如同细胞一般紧凑整齐,邻域特征比较容易表达。这一个优点主要是来源于两个方面,第一是作者将原始图像的 RGB 色彩空间转换成 CIELAB 色彩空间来进行距离度量。

CIELAB 色彩空间

 

RGB 色彩空间

 

在相同的模型参数下,使用 CIELAB 和 RGB 的结果对比可以发现,CIELAB确实可以使得超像素分割出来比较规整。

CILLAB空间分割结果

 

RBG空间分割结果

 

二是作者的 k-mean 距离度量公式中是分别对色彩空间以及欧式空间分别进行计算加权求和,其中有一个权重的度量因子 进行控制使分割出来的结果倾向于空间相似性还是色彩相似性。 越大,空间相似性越重要,超像素的结果越紧凑。 越小,色彩相似性越重要,超像素的结果就会顺着图像的纹理蔓延。

(a) 原图 (b) (c) (d)

 

  1. 运行速度快,可以进行矩阵运算,对大多数图片可以在数十秒内完成分割,因为是基于 k-mean 的算法,所以时间复杂度和其类似,和图片的像素数呈线性关系,并且和超像素的划分数 无关。

    实际使用过程中容易遇到的问题

    基于 k-mean 的方法,由于各个像素点和 k-mean 中心点度量的距离和颜色的欧式距离有关,所以产生的聚类块空间上可能是不连接的,如下图的项链,虽然作者在论文中没有对这种情况进行讨论,但是给出的代码中有对超像素的连接性进行判断,消除掉过小的超像素块。但是这种判断方法是在算法结束之后进行判断的。 第二是由于 SLIC 设置的 搜索空间。虽然作者在论文中设置这个的出发点是为了降低算法的时间复杂度,但是在更新 k-mean 的中心点的时候, 搜索空间会发生位移,这也会间接导致一些像素点在搜索空间上不可达,间接导致超像素不连续或者包含孔洞。

    SLIC 算法分割实例(在进行连通性判断前停止),图中的项链因为色彩形状比较特殊所以超像素分割结果空间上不连续,产生很多孔洞。

     

    SLIC 产生孔洞的一个 toy problem

     


针对经典算法的改进

论文系统全面地对有代表性的超像素算法进行了评测。

Stutz D, Hermans A, Leibe B, et al. Superpixels: An evaluation of the state-of-the-art[J]. Computer Vision and Image Understanding, 2018: 1-27.

作者给出超像素算法大致分为以下几类:

  1. 基于分水岭算法(Watershed-based)
  2. 基于密度算法(Density-based)
  3. 基于图论算法(Graph-based)
  4. 轮廓进化算法(Contour evolution)
  5. 基于路径算法(Path-based)
  6. 基于聚类算法(Clustering-based)
  7. 能量优化算法(Energy optimization)
  8. 基于小波分析(Wavelet-based)

上图是论文作者给出的排名结果。那些考虑了超像素与图像边界损失的算法 CRS, ERS, SEEDS, ERGC 和 ETPS 能够有效的捕获到图像的细节。作者发现基于路径和密度的评估算法以及过分割算法显示出较低的视觉质量。另一方面,基于聚类、轮廓演化和迭代能量优化算法大多表现出良好的边界依从性,有些算法提供了一个紧凑性参数,如SLIC、ERGC和ETPS。

可以看到作者测出来的结果是 ETPS 和 SEEDS 的得分名列前茅,经典的 SLIC 算法虽然简单,但是也是很可靠。下面就来研究一下,ETPS 和 SEEDS 的算法原理来找到得分高的原因是什么。

作者得出的结论是基于路径和密度的评估算法以及过分割算法显示出较低的视觉质量。另一方面,基于聚类、轮廓演化和迭代能量优化算法大多表现出良好的边界依从性,有些算法提供了一个紧凑性参数,如 SLIC 、ERGC 和 ETPS。基于图的算法显示了混合结果—— FH 、CIS 和 PB 等算法显示出较差的边界附着性,而 ERS、RW、NC 和 POISE 显示出较好的边界附着性。然而,良好的边界附着,特别是关于图像中的细节,通常以较低的紧致性、规则性和平滑度为代价,如ETPS 和 SEEDS 所见。此外,紧致性、光滑性和正则性不一定联系在一起,应单独讨论。


SEEDS 算法

Den Bergh M V, Boix X, Roig G, et al. SEEDS: Superpixels Extracted Via Energy-Driven Sampling[J]. International Journal of Computer Vision, 2015, 111(3): 298-314.

算法原理:不用于以往的算法,SEEDS算法初始化直接将图片划分等大小的方格,然后通过后续的步骤调整方格的边界来修正方格里包含的颜色分布。

SEEDS 算法原理过程

作者通过定义一个能量函数 Eq.2,使用爬山法对其进行优化。是用于评估颜色分布能量的项。是用于评估边界能量的项。

颜色能量分布项

经典的概率密度直方图

超像素个体应在视觉上一致,特别是颜色应尽可能均匀。然而,目前还不清楚哪种数学方法是评价一个区域颜色均匀性的最佳方法。所谓的能量这种说法,只是用来评估算法迭代过程中的状态,使其能够用数值来表示,通过爬山法来最大化能量。然后作者采用的度量方法是图像处理中经典的概率密度分布直方图。统计颜色的概率密度分布,然后评估直方图中颜色种类分布多少的一个有效的方法就是熵。当颜色只有一种的时候,熵达到最大为1,其他情况就会比1小,这样就可以使用爬山法来解决。

使用熵值来评估颜色分布是其性能上超过 SLIC 的原因之一,SLIC 使用的是欧几里得距离来度量像素点的相似度,考虑的只是单个像素点和均值中心的关系,均值反应的信息量太少了,比如不能反映颜色的方差,对五彩斑斓的图像区域细节处理起来效果就很差。如上图 SLIC 的项链。在考虑颜色分布使用熵来度量之后能够获得更多的全局信息。

边界能量项

回顾 SLIC 的算法损失 Eq.(1),可以发现 SLIC 对边界的控制其实是隐式的,只是要求像素不能离聚类中心太远,而并没对超像素边界紧凑度和平滑度进行显式控制。

利用颜色能量分布项的设计思想,稍微改造一下就可以用来构造边界能量项,所以 SEEDS 算法做的工作就是以每一个像素点为中心,构造其周围 的正方形区域信息。统计其中包含的超像素种数的概率密度分布,同样的使用熵来评估。同理可以得出当熵比较高的时候,这个像素周围的超像素的种数单一,说明边界比较规整。

算法复杂度

SEEDS算法每次迭代只对处于超像素边界的像素点进行更新,通过能量函数的值来决定这个像素点是否转移到相邻的超像素块内。

每次的迭代都只会用到超像素边界的图像像素点,时间复杂度为 。使用爬山法来贪心地进行更新状态,当且仅当能量函数能增加的时候。所以这里作者进行了一个优化:只需要判断新的状态的能量函数是否增加。而不需要具体地去计算出熵的值是多少。

交叉距离

作者通过精心构造的能量函数的表达式,通过证明可以使用通过交叉距离(intersection distance)来判断两个直方图的熵值大小。这样就可以高效地帮助爬山法判断是否应该进行更新边界,而不用重新地去计算整个直方图的熵(这样会导致计算量巨大,不能满足超像素算法要求的高效性)。具体的证明需要去看作者的论文。

至此SEEDS算法每轮地迭代的时间复杂度都可以在线性的时间复杂度内完成。


ETPS 算法

Yao J, Boben M, Fidler S, et al. Real-time coarse-to-fine topologically preserving segmentation[C]. computer vision and pattern recognition, 2015: 2947-2955.

claim 点

这篇文章最主要是汲取了 SEEDS 和 SLIC 双方的优点,提出的是一种基于马尔科夫随机场的边缘像素交换的方法。

马尔科夫随机场(MRF)

https://zhuanlan.zhihu.com/p/38343732

ETPS 论文的核心算法是基于马尔科夫随机场(MRF)。MRF 是无向图模型,所表达的联合概率模型在团内的节点存在,在团之间是不存在依赖关系的。无向图的两个节点之间有边相连说明有依赖关系,但是并没有先后顺序的关系。所以 MRF 经常用图像方面,每个像素都可以看成是无向图中的节点,像素的颜色和其领域有十分大的依赖关系,但是和远处的节点的关联性就大大降低了,所以估计某个像素点的属性可以通过计算4邻域或者是8邻域的像素点的属性来估计。

MRF 建模图像处理

超像素是图像分割的一种变种,超像素分割属于图像分割(image segmentation)之中的过分割(over segmentation)。而图像分割的本质上就是图像聚类,将图像中相似的像素点进行聚合,相当于分配一个标签(每一个超像素就是一种标签类型)。利用 MRF 进行图像分割的一种方案就是通过迭代的方法最大化似然函数来更新像素点所属的类别。

针对 SLIC 产生超像素不连续问题的改进

作者指出 SLIC 生成超像素不连续的问题的根源来自于 k-mean 算法本身,很难在基于 k-mean 算法上解决这个问题。SEEDS 只对超像素边缘像素交换的策略是一个非常好的解决办法。

针对 SEEDS 方法的改进

SEEDS 的能量函数的提出是比较新颖的策略,文章附录是 SEEDS 作者亲自通过证明基于概率密度直方图的熵能够行得通的。成也萧何败萧何,新方法虽然值得提倡,但是能够用上熟悉的老方法就好了,毕竟老方法是经过了很深的积淀,理论基础完善。所以作者借助于成熟的 MRF 模型的势能函数来构造能量函数,理论有保障,所以 ETPS 作者就省去了证明的步骤了。

另一个是 ETPS 作者发现了 SEEDS 中一个尚不完善的问题就是更新边界的像素的时候会产生一些非法的状态转移,文章中特地指出了这一点并进行了讨论。

图中红黄蓝分别代表三个超像素,当?像素发生转移(变成黄色或者红色类)的时候,蓝色超像素就会断裂,所以状态转移的时候需要禁止掉。

一个一笔带过的改进点就是说到,由粗到细的更新策略,由粗粒度(大矩形区域)到细粒度(小矩形区域),一是速度快,二是更容易找到更有解。

ETPS 算法过程

ETPS 算法粒度由粗到细过程,背景中红色的线条表示划分的边界,这个边界是由一个粗粒度的 k-mean 的算法确定的,相当于已经划分了很多粗粒度的超像素。在划分好红色边界之后,采用的是由粗到细的更新策略,背景中灰色的矩形表示的是当前的更新粒度。算法每次迭代的时候,首先需要确定一遍哪些灰色小矩形和细线是有关的,需加入一个队列里备用。然后采取和 SEEDS 算法的策略,根据作者定义好的能量函数计算,确定是否转移到相邻的超像素上,这样每次都只会更新到和边界有关的部分,具体作者还禁止了非法的状态转移操作,从根源杜绝了超像素产生孔洞或者不连续的问题。当队列为空的时候就完成了一次迭代,切换到更细的粒度来重复迭代。